//
//  yx_sort.c
//  algorithm
//
//  Created by hao on 2018/4/16.
//  Copyright © 2018年 hao. All rights reserved.
//

#include "yx_sort.h"
#include <time.h>

void printf_values(int values[], int count);

enum SortType {
    desc_order, asc_order
};

/** 冒泡排序 */
void bubble_sort(int values[], int count)
{
    int temp, repeat = 0;
    for (int i = 0; i < count; i++) {
        for (int j = 0; j < count - 1 - i; j++) {
            // 从大到小排序
            if (values[j] < values[j+1]) {
                temp = values[j];
                values[j] = values[j+1];
                values[j+1] = temp;
            }
            repeat++;
        }
    }
    printf_values(values, count);
    count = 0;
    for (int i = 0; i < count; i++) {
        for (int j = 0; j < count-1-i; j++) {
            // 从小到大排序
            if (values[j] > values[j+1]) {
                temp = values[j+1];
                values[j+1] = values[j];
                values[j] = temp;
            }
            repeat++;
        }
    }
    printf("repeat count = %d \n", repeat);
}

/** 快速排序 */
void quick_sort(int values[], int start, int end)
{
    // -1. 必须校验
    if (start >= end) {
        return ;
    }
    // 0. 临时保存start和end的值
    int left = start;
    int right = end;
    // 1. 取基准数key(该值可随机取)，默认取start位置
    int key = values[start];
    // 2. 从右往左扫描、从左往右扫描各一次才算做一个循环,条件是start<end
    while (start < end) {
        // 3. 必须先从右往左循环扫描，不然会死循环，当扫描到values[end]>=key(如果<=key即降序)的值就跳出当次循环，end的值覆盖start的值，因为start的值已经被取出即key，否则end--
        while (start < end && values[end] >= key) {
            end--;
        }
        values[start] = values[end];
        // 4. 循环从左往右扫描，当扫描到values[start]<=key(如果>=key即降序)的值就跳出当次循环，start的值覆盖end的值，因为end的值已经在第3步的循环中赋值给start位置的值，否则start--
        while (start < end && values[start] <= key) {
            start++;
        }
        values[end] = values[start];
    }
    // 5. 当start>=end跳出最外层循环，将key赋值到start或end位置
    values[end] = key;
    printf_values(values, 9);
    // 6. 递归调用，一个向左，一个向右，不包括start位置本身
    quick_sort(values, left, start-1);
    quick_sort(values, start+1, right);
}

/** 归并排序 */
void merge_sort(int values[], int start, int end)
{
    // 1. 分解
    int mid = -1, lave = -1;
    while (start < end) {
        mid = end*0.5;
        lave = end-mid;
        printf("0->%d->%d, %d->%d->%d \n", mid, mid-0, mid, end, lave);
    }
    // 2. 合并
}

void printf_values(int values[], int count)
{
    printf("start:\t");
    for (int i = 0; i < count; i++) {
        printf("%d\t", values[i]);
    }
    printf("end \n");
}

void yx_sort_demo()
{
    clock_t start,finish;
    double totaltime;
    start = clock();
    
    int count = 9;
    int values[] = {5, 0, 1, -3, -5, 6, 9, -5, 7};
    printf_values(values, count);
//    bubble_sort(values, count);
//    quick_sort(values, 0, count-1);
    merge_sort(values, 0, count-1);
    printf_values(values, count);
    
    finish = clock();
    totaltime = (double)(finish-start)/CLOCKS_PER_SEC;
    printf("程序运行的时间为: %f 秒 \n", totaltime);
}
